package leetcode.day_2021_03_15_2021_03_21;

import leetcode.Head;
import leetcode.ListNode;

import java.util.List;

/**
 * 61. 旋转链表
 * https://leetcode-cn.com/problems/rotate-list/
 */
public class LeetCode0061 {

    public static ListNode rotateRight(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;
        while (--k >= 0 && fast.next!=null) {
            fast = fast.next;
        }

        if (fast.next==null && k==0) {
            return head;
        } else if (k <= 0) {
            while (fast.next != null) {
                slow = slow.next;
                fast = fast.next;
            }
            ListNode newHead = slow.next;
            slow.next = null;
            fast.next = head;
            return newHead;
        } else if (k > 0) {
            return reverse(head);
        }
        return null;
    }

    public static ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        } else if (head.next == null) {
            return head;
        }
        ListNode front = head;
        ListNode cur = head.next;
        ListNode next;
        front.next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = front;
            front = cur;
            cur = next;
        }
        return front;
    }

    public static ListNode rotateRight2(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }

        ListNode oldTail = head;
        int n;
        for(n=1; oldTail.next!= null; n++) {
            oldTail = oldTail.next;
        }
        oldTail.next = head;

        ListNode newTail = head;
        for (int i=0; i<n-k%n-1; i++) {
            newTail = newTail.next;
        }

        ListNode newHead = newTail.next;
        newTail.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        ListNode head = rotateRight2(Head.genListEven(), 2);
//        ListNode head = reverse(Head.genListEven());
        Head.printList(head);
    }
}
